package interviewClassic150;

import org.junit.Test;

import java.util.Arrays;

public class CanCompleteCircuit {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //计算每个的差值（到下个节点还剩多少油）
        int n = gas.length;
        int[] rest = new int[n];
        for (int i = 0; i < n; i++) {
            rest[i] = gas[i] - cost[i];
        }
        //计算是否能跑完整圈
        int sum = Arrays.stream(rest).sum();
        if (sum < 0) return -1;

        //能跑完
        /*
        假设从起点跑到0位置没有缺油，设为x，接下来从0跑到起点油耗为y
        x+y>=0,x>=0
        y<-|x|绝对值不可能
        那么是否有可能y=y1+y2+y3+...
        x+y1 < 0 ?
        那么就是x = y2 + y3 + x（原），y2到yn中肯定会有个特别大的
        那我们从前依次向后找，这种会在第一时间确定
        */
        //从起点看是否会出现缺油的情况
        int resIndex = 0;
        int store = 0;
        int i = resIndex;
        while (i < n) {
            store += rest[i];
            if (store < 0) {
                //出现缺油情况，重置起点
                //重置resIndex
                //从新起点到数组终点的储油量会被放大
                resIndex = i + 1;
                store = 0;
            }
            i++;
        }

        return resIndex;
    }

    @Test
    public void test() {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        int i = canCompleteCircuit(gas, cost);
        System.out.println(i);
    }
}
